#pragma once

namespace AVL
{
	/*template<class K,class V>*/
	//struct pair
	//{
	//	K first;
	//	V second;
	//	pair(K _first, V _second)
	//		:first(_first)
	//		, second(_second)
	//	{}
	//	pair(const pair<K, V>& con)
	//		:first(con.first)
	//		, second(con.second)
	//	{}
	//};
	template<class K,class V>
	struct AVLTreeNode
	{
		AVLTreeNode<K, V>* _parent;
		AVLTreeNode<K, V>* left;
		AVLTreeNode<K, V>* right;

		pair<K, V> data;
		int bf;   //平衡因子         右字树减左子树

		AVLTreeNode(const pair<K, V>& con)
			:data(con)
			, _parent(nullptr)
			, left(nullptr)
			, right(nullptr)
			, bf(0)
		{}
	};

	template<class K,class V>
	class AVLTree
	{
		typedef AVLTreeNode<K, V> Node;
	private:
		Node* root;
	public:
		AVLTree() :root(nullptr)
		{}
		void RotaR(Node* cur)
		{
			//右单旋
			Node* parent = cur->_parent;
			Node* SubL = cur->left;
			Node* SubLR = SubL->right;

			cur->left = SubLR;
			if (SubLR != nullptr)
			{
				SubLR->_parent = cur;
			}
			SubL->right = cur;
			cur->_parent = SubL;

			if (cur == root)
			{
				root = SubL;
				SubL->_parent = nullptr;
			}
			else
			{
				if (parent->left == cur)
					parent->left = SubL;
				else
					parent->right = SubL;

				SubL->_parent = parent;
			}

			SubL->bf = cur->bf = 0;
		}
		void RotaL(Node* cur)
		{
			//左单旋
			Node* parent = cur->_parent;
			Node* SubR = cur->right;
			Node* SubRL = SubR->left;

			cur->right = SubRL;
			if (SubRL != nullptr)
			{
				SubRL->_parent = cur;
			}
			SubR->left = cur;
			cur->_parent = SubR;

			if (cur == root)
			{
				root = SubR;
				SubR->_parent = nullptr;
			}
			else
			{
				if (parent->left == cur)
					parent->left = SubR;
				else
					parent->right = SubR;
				SubR->_parent = parent;
			}

			SubR->bf = cur->bf = 0;
		}
		bool Insert(const pair<K,V>& con)
		{
			if (root == nullptr)
			{
				//root 为空
				root = new Node(con);
				return true;
			}
			//二叉搜索树，找到合适的位置插入
			Node* parent = nullptr;
			Node* cur = root;
			while (cur)
			{
				if (cur->data.first < con.first)
				{
					parent = cur;
					cur = cur->right;
				}
				else if (cur->data.first> con.first)
				{
					parent = cur;
					cur = cur->left;
				}
				else
				{
					//相等
					return false;
				}
			}  //出循环

			Node* child = new Node(con);
			//判断插入哪边
			if (parent->data.first<con.first)	
			{
				//小于，插入右边
				parent->right = child;
				child->_parent = parent;
			}
			else
			{
				//大于，插入左边
				parent->left = child;
				child->_parent = parent;
			}

			//插入后修改平衡因子

			while (parent)
			{
				//先判断是哪边插入
				if (parent->left == child)
				{
					//左边
					parent->bf--;
				}
				else
				{
					//右边
					parent->bf++;
				}
				
				//判断bf合理否，还是继续迭代否
				if (parent->bf == 0)
				{
					//子树没有改长度
					break;
				}
				else if (parent->bf == -1 || parent->bf == 1)
				{
					//子树高度增加，往上更改bf
					child = parent;
					parent = parent->_parent;
				}
				else if (parent->bf==-2||parent->bf==2)
				{
					//不合理,需旋转平衡

					//旋转的四种情况
					Node* SubL = parent->left;
					Node* SubR = parent->right;
					if (parent->bf == -2 && SubL->bf == -1)
					{
						//右单旋
						RotaR(parent);
					}
					else if (parent->bf == 2 && SubR->bf == 1)
					{
						//左单旋
						RotaL(parent);
					}
					else if (parent->bf == -2 && SubL->bf == 1)
					{
						//保存值，为修改平衡因子分类
						Node* SubLR = SubL->right;
						int bnf = SubLR->bf;

						//先对SubL 左单旋，再右单旋
						RotaL(SubL);
						RotaR(parent);

						//视情况修改平衡因子
						if (bnf == 0)
						{
							SubLR->bf = 0;
							SubL->bf = 0;
							parent->bf = 0;
						}
						else if (bnf == 1)
						{
							//插入右边
							SubLR->bf = 0;
							SubL->bf = -1;
							parent->bf = 0;
						}
						else if (bnf == -1)
						{
							//插入左边
							SubLR->bf = 0;
							SubL->bf = 0;
							parent->bf = 1;
						}
						else
						{}
					}  //出双旋
					else if (parent->bf == 2 && SubR->bf == -1)
					{
						Node*SubRL = SubR->left;
						int bnf = SubRL->bf;
						//先对SubR 右单旋，再左单旋
						RotaR(SubR);
						RotaL(parent);

						//视情况修改平衡因子
						if (bnf == 0)
						{
							SubRL->bf = 0;
							SubR->bf = 0;
							parent->bf = 0;
						}
						else if (bnf == 1)
						{
							SubRL->bf = 0;
							SubR->bf = 0;
							parent->bf = -1;
						}
						else if (bnf == -1)
						{
							SubRL->bf = 0;
							SubR->bf = 1;
							parent->bf = 0;
						}
						else
						{}
					}//出双旋
					else
					{}
					break;
				}
				else
				{
					//出错
				}
				
			}   //出修改平衡因子循环
			return true;
		}  //出插入

		int Height(Node* root)
		{
			if (root == nullptr)
			{
				return 0;
			}
			int left = Height(root->left);
			int right = Height(root->right);
			return (left > right ? left : right) + 1;
		}
		bool _IsBlance(Node* root)
		{
			if (root == nullptr)
			{
				return true;
			}
			int leftTree = Height(root->left);
			int rightTree = Height(root->right);
			if (rightTree - leftTree != root->bf)
			{
				cout <<  root->data.first<<endl;
			}
			
			return abs(leftTree - rightTree) < 2
				&& _IsBlance(root->left)
				&& _IsBlance(root->right);
		}
		//判断是否平衡
		bool IsBlance()
		{
			return _IsBlance(root);
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->left);
			std::cout << root->data.first << " ";
			_InOrder(root->right);
		}
		void InOrder()
		{
			_InOrder(root);
			std::cout << std::endl;
		}
	};
}